package leetcode.递归回溯BFSDFS.通过建模解决问题;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 279. 完全平方数
 * <p>
 * 当每一次都可以判断出多种情况，有多次的时候就适合用 BFS-广度优先遍历
 * 使用 BFS 应注意：
 * 队列：用来存储每一轮遍历得到的节点；
 * 标记：对于遍历过的节点，应该将它标记，防止重复遍历。
 * <p>
 * 我们将它第一个平方数可能出现的情况做分析 只要 i * i < n 就行
 * 再在此基础上进行二次可能出现的平方数分析
 * 注意：为了节省遍历的时间，曾经（ n - 以前出现的平方数） 这个值出现过，则在此出现这样的数时直接忽略。
 */
public class Test279完全平方数 {

    public static void main(String[] args) {
        System.out.println(numSquares(123583));
    }

    static class Node {
        int val;
        int step;

        public Node(int val, int step) {
            this.val = val;
            this.step = step;
        }
    }

    /**
     * 脑子里想象解析图是怎么创建的
     * 若 X、Y 之间相差一个完全平方数，就建立一条边
     * 例如 n = 6
     * 只有 1 和 4 是在 6 范围内的完全平方数
     * 所以把 6 和 5、2 连接起来
     *
     * 然后再找 5、2 到 0 的最短路径，如此下去直到找到 0
     *
     * 一边往下找的时候，一边累加从 6 开始到这个节点的路径长度
     * 那么找到 0 时的路径长度就是答案
     * 
     * @param n
     * @return
     */
    public static int numSquares(int n) {
        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(n, 0));
        // 其实一个真正的图的 BSF 是一定会加上 visited 数组来过滤元素的
        boolean[] visited = new boolean[n + 1];
        while (!queue.isEmpty()) {
            int num = queue.peek().val;
            int step = queue.peek().step;
            queue.remove();
            // 每一层的广度遍历
            for (int i = 1; ; i++) {
                /*
                 下面代码的意思是：图中从节点n开始探索有几个完全平方数在n的范围内
                 且存储：用n减去这些完全平方数后得到的值
                 然后把n和该值连上一条线
                  */
                int nextVal = num - i * i; // 在剩下的数字里面接着找完全平方数
                // 说明已达最大平方数
                if (nextVal < 0) {// 例如 4-1*1=3 大于0,1是第一个最小的完全平方数，而4-3*3=-5 就表示3已经超过了最大平方数
                    break;
                }
                // 由于是广度遍历，所以当遍历到0时，肯定是最短路径
                if (nextVal == 0) {// 例如：4-2*2=0 表示节点4已经连接上0了，节点4的最短路径找到了
                    return step + 1;
                }
                // 由于存在重复子问题，用数组记录新产生的值
                if (!visited[nextVal]) {
                    queue.add(new Node(nextVal, step + 1));
                    visited[nextVal] = true;
                }
            }
        }
        return -1;
    }
}
